package com.itheima.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 四数之和
 */
public class SumLeetcode18 {

    public static void main(String[] args) {
        int[] candidates = {1000000000, 1000000000, 1000000000, 1000000000}; // 解决溢出问题
//        int[] candidates = {1, 0, -1, 0, -2, 2};
//        int[] candidates = {2, 2, 2, 2, 2};
        System.out.println(fourSum(candidates, -294967296));
    }

    static List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        dfs(4, 0, nums.length - 1, target, nums, new LinkedList<>(), result);
        return result;
    }

    static void dfs(int n, int i, int j, long target, int[] nums,
                    LinkedList<Integer> stack,
                    List<List<Integer>> result) {
        if (2 == n) {
            // 套用两数字之和求解
            twoSum(i, j, nums, target, stack, result);
            return;
        }

        for (int k = i; k < j - (n - 2); k++) { // 剪枝 四数之和 i < j-2 三数之和 i < j-1
            // 检查重复
            if (i < k && nums[k] == nums[k - 1]) { // i < k 是越界检查，组合无重复
                continue;
            }
            stack.push(nums[k]);
            dfs(n - 1, k + 1, j, target - nums[k], nums, stack, result);
            stack.pop();
        }
    }

    /*
        思路
         - 两个指针 i 和 j 分别指向最左侧和最右侧的数字
         - 它俩指向的数字和 target 相比
            - 大于 target i++ 向右找
            - 小于 target j-- 向左找
            - 等于 target 找到
    */
    public static void twoSum(int i, int j, int[] nums, long target,
                              LinkedList<Integer> stack,
                              List<List<Integer>> result) {
        while (i < j) {
            int sum = nums[i] + nums[j];
            if (target > sum) {
                i++;
            } else if (target < sum) {
                j--;
            } else { // 找到解
                ArrayList<Integer> list = new ArrayList<>(stack);
                list.add(nums[i]);
                list.add(nums[j]);
                result.add(list);
                // 继续查找其他的解
                i++;
                j--;
                while (i < j && nums[i] == nums[i - 1]) {
                    i++;
                }
                while (i < j && nums[j] == nums[j + 1]) {
                    j--;
                }
            }
        }
    }
}
